package 二叉树题目.在二叉树中找到两个节点的最近公共祖先;

import java.util.Deque;
import java.util.LinkedList;

public class Solution {

    /**
     * 递归-->在二叉树中找到两个节点的最近公共祖先
     * @param root
     * @param o1
     * @param o2
     * @return
     */
    public int lowestCommonAncestor1 (TreeNode root, int o1, int o2) {
        // write code here
        if(root == null){
            return -1;
        }
        if (root.val == o1 || root.val == o2){
            return root.val;
        }
        // 根节点不等于 o1 或者 o2
        int leftRet = lowestCommonAncestor1(root.left,o1,o2);
        int rightRet = lowestCommonAncestor1(root.right, o1,o2);
        if (leftRet == -1 && rightRet == -1){  // 左右都为空
            return -1;
        }else if(leftRet == -1){                // 左边没找到，就在右子树
            return rightRet;
        }else if (rightRet == -1){             // 右边没找到， 就在左子树
            return leftRet;
        }
        // 此时左右都存在，则返回当前的根节点
        return root.val;
    }

    /**
     * 非递归---->在二叉树中找到两个节点的最近公共祖先
     * @param root
     * @param o1
     * @param o2
     * @return
     */
    public int lowestCommonAncestor2 (TreeNode root, int o1, int o2) {
        // 1.获得路径
        Deque<TreeNode> stack1 = new LinkedList<>();
        getPath(root,o1,stack1);
        Deque<TreeNode> stack2 = new LinkedList<>();
        getPath(root,o2,stack2);
        // 2.比较两个栈大小
        int size = Math.abs(stack1.size()-stack2.size());
        if (stack1.size()>stack2.size()){
            for (int i = 0; i < size; i++) {
                stack1.pop();
            }
        }else {
            for (int i = 0; i < size; i++) {
                stack2.pop();
            }
        }
        // 3.对两个栈进行对比
        while (!stack1.isEmpty() && !stack2.isEmpty()){
            int ret1 = stack1.pop().val;
            int ret2 = stack2.pop().val;
            if (ret1 == ret2){
                return  ret1;
            }
        }
        return -1;

    }

    public static boolean getPath(TreeNode root, int target, Deque<TreeNode> stack){
        if (root == null){
            return false;
        }
        stack.push(root);
        if (root.val == target){
            return true;
        }
        boolean ret1 = getPath(root.left,target,stack);
        if (ret1){
            return true;
        }
        boolean ret2 = getPath(root.right,target,stack);
        if (ret2){
            return true;
        }
        stack.pop();
        return false;
    }

}
